{T}

如何透彻理解 Paxos 算法？

0. 引言

Paxos 是分布式共识算法的"鼻祖"，由 Leslie Lamport 于 1990 年提出（论文《The Part-Time Parliament》）。它解决的问题是：在可能发生故障、网络分区的节点集合中，如何让所有节点对一个值达成一致。ZooKeeper 的 ZAB、Raft 都是 Paxos 的简化/变体。理解 Paxos 的两阶段流程与多数派思想，是看懂一切共识协议的基础。

1. 问题定义与角色

1.1 共识问题

分布式系统需要多个节点对同一件事（选主、日志内容、配置值）达成一致，且要求：

  • 安全性（Safety）：已达成一致的值不再改变；不同节点不会得出不同结论；
  • 活性（Liveness）：系统最终能达成一致（不无限阻塞）。

1.2 三个角色

角色职责
Proposer（提议者）提出提案 (编号 n, 值 v)，推动共识
Acceptor（接受者）投票/存储提案，决定是否接受；通常对应存储节点
Learner（学习者）学习"哪个值被多数派接受"，不参与投票

实际节点往往一职多兼：比如 5 节点 ZooKeeper 集群中，每个节点既是 Proposer 也是 Acceptor，Leader 是获胜的 Proposer。

2. 两阶段的核心流程

Paxos 的核心是两阶段 + 多数派：

图表渲染中…

2.1 Phase 1：Prepare / Promise

  1. Proposer 生成全局递增编号 n，向半数以上 Acceptor 发送 Prepare(n)；
  2. Acceptor 收到后：
    • 若 n 大于自己见过的最大编号 max_n，则承诺不再接受编号小于 n 的提案，并回复 Promise(n, 已接受的最大编号提案)（若无则返回空）；
    • 否则拒绝（回复 reject）。

2.2 Phase 2：Accept / Accepted

  1. Proposer 收集多数派 Promise 后：
    • 若没有任何 Acceptor 返回过已接受提案 → 自由选择自己的值 v；
    • 若有 → 必须采用编号最大的那个已接受提案的值（这是安全性的关键：新提案必须延续已达成共识的值）；
  2. 向这些 Acceptor 发送 Accept(n, v)；
  3. Acceptor 若未违反承诺（n >= max_n）则接受并持久化，回复 Accepted(n, v)。

为什么必须选编号最大的已接受值？ 因为那个值可能已经被多数派接受、即将达成共识。若 Proposer 提出新值，会破坏"已达成一致的值不再改变"的安全性。

3. 安全性论证与活锁问题

3.1 为什么多数派能保证安全

任意两个多数派必有交集（如 3 节点中 2/3 与 2/3 至少重叠 1 个节点）。通过"承诺不再接受更小编号"+"新提案继承已接受值"，任何已达成共识的值都会沿着编号链被传递下去，从而保证不会出现两个不同值同时达成共识（B 值覆盖 A 值场景下，A 值一定是"未真正达成共识"的）。

3.2 活锁：Paxos 的阿喀琉斯之踵

两个 Proposer 交替发起更高编号的 Prepare，导致对方的 Accept 一直被新承诺拒绝：

text
P1: Prepare(1) → 多数派 Promise
P2: Prepare(2) → 多数派 Promise（覆盖 P1 的承诺）
P1: Accept(1,v1) → 被拒绝（已有承诺 2）
P1: Prepare(3) → 多数派 Promise（覆盖 P2）
P2: Accept(2,v2) → 被拒绝
... 无限循环，永远无法达成共识（活性失败）

解法：引入Leader 选举——同一时刻只有一个 Proposer 在提提案（选举出的 Leader），活锁自然消失。这就是 Multi-Paxos 的出发点。

4. Multi-Paxos：工程化的 Paxos

Basic Paxos 每达成一个值都要两轮 RPC，代价高。工程实现（Chubby、ZAB、Raft）普遍采用 Multi-Paxos：

  1. 选主：先通过一轮 Paxos 选出 Leader（固定 Proposer）；
  2. 免 Prepare：Leader 任期（epoch/term）内跳过 Phase 1，直接 Accept（多数派已承诺该任期）；
  3. 日志复制：每个提案对应日志中的一个槽位（instance），Leader 按序提交，Follower 按序应用；
  4. Learner 收敛：多数派接受即提交，其余节点从 Leader 或已提交节点补日志。
图表渲染中…

5. Paxos vs Raft

维度Paxos（Multi-Paxos）Raft
提出者Lamport（1990）Ongaro & Ousterhout（2014）
设计目标理论共识算法可理解、可教学的工程协议
选主未定义（需自行实现）明确定义：任期 term + 心跳超时随机化
日志复制槽位管理复杂强制日志连续性：nextIndex 逐条对齐
成员变更未定义联合共识（joint consensus）
代表实现Chubby、ZAB（变体）etcd、Consul、TiKV、K8s apiserver

Raft 不是新算法，而是将 Multi-Paxos 的模糊地带（选主、日志对齐、成员变更）全部显式化的工程化产物——这也是"Raft 更容易实现"的原因。

6. 小结

  • Paxos 用两阶段（Prepare/Accept）+ 多数派交集保证：已共识的值不变、不会出现双值共识；
  • 新提案必须继承已接受的最大编号提案值——这是安全性核心；
  • 活锁源于多个 Proposer 竞争，Leader 化（Multi-Paxos）是工程标配；
  • Multi-Paxos 的 Leader → 日志复制 → 提交收敛，是 ZAB、Raft 的共同骨架；
  • 面试高频：能画出两阶段时序图、说清"为什么选最大编号值"、对比 Raft 的差异。

下一章讲解 ZooKeeper 的一致性保证：ZAB 协议四阶段与 FastLeaderElection 选主机制。